package leetcode;

public class LeetCode109 {
    // 找到中间的指针
    public TreeNode sortedListToBST(ListNode head) {
        if (head==null)
            return null;
        ListNode slow = head, quirk = head;
        while (quirk != null && quirk.next != null) {
            slow = slow.next;
            quirk = quirk.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        TreeNode current = root;
        ListNode p = head;
        while (p != slow) {
            TreeNode node = new TreeNode(p.val);
            if (p.val < current.val) {
                current.left = node;
                current = current.left;
            } else {
                current.right = node;
                current = current.right;
            }
            p = p.next;
        }
        ListNode q = slow.next;
        current = root;
        while (q != null) {
            TreeNode node = new TreeNode(q.val);
            current.right = node;
            current = current.right;
            q = q.next;
        }
        return root;
    }
//------------------------------------------------------------------
}
